A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
This invention relates to techniques for encoding finite state machine (FSM) data structures. More specifically, this invention relates to the storage of an FSM data structure in a compact encoded form.
U.S. Pat. Nos. 4,241,402 and 4,285,049 each relate to a finite state automaton which receives signals and, based on the received signals and on control tables, steps from a present state along a transition to a next state, eventually reaching a report state dependent on the received signal sequence. The signals may, for example, be a sequence of character elements. The control tables contain information from a finite state machine ("FSM") data structure. In general, FSM data structures include information about states and transitions between states, and the information in a specific data structure may be encoded in many ways. The encodings disclosed in U.S. Pat. Nos. 4,241,402 and 4,285,049 are conventional in that each unit of data, there called a state word, includes part of a state control table which controls the transitions from a specific state to other states. The state word may include, for example, a memory address used to obtain the address of a following state word.
It would be advantageous to have a way to encode an FSM data structure more compactly than can be achieved with the conventional techniques without sacrificing any of the information in the data structure.